import copy

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        result = []

        def traverse(i, current):
            # the correct condition
            if len(current)==4 and i==len(s): result.append(copy.copy(current))
            # index out of range
            if i>=len(s): return
            # current out of range
            if len(current)>=4: return
            # invalid split
            if s[i]=='0':
                current.append('0')
                traverse(i+1, current)
                current.pop()
            else:
                for j in range(1,4):
                    w = s[i:i+j]
                    if 0<=int(w)<=255:
                        current.append(w)
                        traverse(i+j, current)
                        current.pop()
        
        traverse(0, [])
        return ['.'.join(ret) for ret in result]

print(Solution().restoreIpAddresses("11111111111111111111111111111111111111"))
